package Leetcode.贪心;

import java.util.Comparator;
import java.util.PriorityQueue;

class HuffmanNode {
    int frequency;
    char data;
    HuffmanNode left, right;

    public HuffmanNode(int frequency, char data) {
        this.frequency = frequency;
        this.data = data;
    }
}

class HuffmanComparator implements Comparator<HuffmanNode> {
    public int compare(HuffmanNode x, HuffmanNode y) {
        return x.frequency - y.frequency;
    }
}

public class HuffmanCoding {

    public static void printCode(HuffmanNode root, String s) {
        if (root.left == null && root.right == null && Character.isLetter(root.data)) {
            System.out.println(root.data + " : " + s);
            return;
        }
        printCode(root.left, s + "0");
        printCode(root.right, s + "1");
    }

    public static void main(String[] args) {
        char[] charArray = { 'a', 'b', 'c', 'd', 'e', 'f' };
        int[] charFreq = { 5, 9, 12, 13, 16, 45 };

        int n = charArray.length;
        PriorityQueue<HuffmanNode> queue = new PriorityQueue<>(n, new HuffmanComparator());

        for (int i = 0; i < n; i++) {
            HuffmanNode node = new HuffmanNode(charFreq[i], charArray[i]);
            queue.add(node);
        }

        HuffmanNode root = null;
        while (queue.size() > 1) {
            HuffmanNode x = queue.peek();
            queue.poll();
            HuffmanNode y = queue.peek();
            queue.poll();
            HuffmanNode f = new HuffmanNode(x.frequency + y.frequency, '-');
            f.left = x;
            f.right = y;
            root = f;
            queue.add(f);
        }
        printCode(root, "");
    }
}
